package com.xinwei.leetcode.数组;

// https://leetcode-cn.com/problems/next-permutation/
public class _31_下一个排列 {
    public static int[] nextPermutation(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int flag = 0; // 用来记录数列是否为全降序

        // 第一步，从右往左扫描，扫描到第一个顺序对则停下
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                left = i;
                flag = 1; // 不是全降序
                break;
            }
        }

        // 第二部，从右往左扫描，扫描下第一个比 left 大的值（就是比他大的值中的最小值）
        for (int i = len - 1; i > left; i--) {
            if (nums[i] > nums[left]) {
                right = i;
                break;
            }
        }

        // 第三步，交换 left 和 right 的值，把 left 右边的全部进行排序（因为已经是逆序，所以用双指针交换最快）
        if (flag == 1) {
            swap(nums, left,right);

            left++;
            right = len - 1;
        }

        while (right > left) {
            swap(nums, left++, right--);
        }
        return nums;
    }

    private static void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

}
